package com.smh;

import com.smh.interfaces.Priority;
import com.smh.interfaces.Queue;
import org.junit.jupiter.api.Test;

/**
 * @author shiminghui
 * @date 2025/2/17 20:47
 * @description: TODO
 */
public class _025_优先级数组_有序 {

    @Test
    public void test1() {

        PriorityQueue<Entry<Integer>> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Entry<>(1, 1));
        priorityQueue.offer(new Entry<>(2, 2));
        priorityQueue.offer(new Entry<>(3, 3));
        priorityQueue.offer(new Entry<>(4, 4));
        priorityQueue.offer(new Entry<>(5, 5));
        Entry<Integer> poll = priorityQueue.poll();
        System.out.println(poll.value());
        priorityQueue.offer(new Entry<>(6, 1));
        poll = priorityQueue.poll();
        System.out.println(poll.value());
        poll = priorityQueue.poll();
        System.out.println(poll.value());
        poll = priorityQueue.poll();
        System.out.println(poll.value());
        poll = priorityQueue.poll();
        System.out.println(poll.value());


    }


    private static class PriorityQueue<T extends Priority> implements Queue<T> {
        private final T[] array;
        private int size;
        private int capacity;

        @SuppressWarnings("unchecked")
        public PriorityQueue(int capacity) {
            this.capacity = capacity;
            array = (T[]) new Priority[capacity];
        }

        public PriorityQueue() {
            this(10);
        }

        @Override
        public boolean offer(T value) {
            if (isFull()) {
                return false;
            }
            int i;
            for (i = size - 1; i >= 0; i--) {
                if (array[i].priority() > value.priority()) {
                    array[i + 1] = array[i];
                } else {
                    break;
                }
            }
            array[i + 1] = value;
            size++;
            return true;
        }

        @Override
        public T poll() {
            if (isEmpty()) {
                return null;
            }
            T t = array[size - 1];
            array[size - 1] = null;
            size--;
            return t;
        }

        @Override
        public T peek() {
            if (isEmpty()) {
                return null;
            }
            return array[size - 1];
        }

        @Override
        public boolean isEmpty() {
            return size == 0;
        }

        @Override
        public boolean isFull() {
            return size == capacity;
        }


    }

    private class Entry<T> implements Priority {
        private T value;
        private int priority;

        public Entry(T value, int priority) {
            this.value = value;
            this.priority = priority;
        }

        private Entry() {
        }

        public T value() {
            return value;
        }

        @Override
        public int priority() {
            return priority;
        }
    }

}
